// 6.45 编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"
tree *fun_6_45_1(tree *root, int key)
{
    if (root)
    {
        if (root->data == key)
            return root;
        else
        {
            tree *l = fun_6_45_1(root->left, key);
            tree *r = fun_6_45_1(root->right, key);
            if (l && l->data == key)
                return l;
            else if (r && r->data == key)
                return r;
            else
                return NULL;
        }
    }
}
void fun_6_45_2(tree *&root)
{
    if (root)
    {
        fun_6_45_2(root->left);
        fun_6_45_2(root->right);
        root = NULL;
        free(root);
    }
}
void fun_6_45(tree *root, int key)
{
    // 1.location
    tree *p = fun_6_45_1(root, key);
    // 2.delete
    fun_6_45_2(p);
}

int main()
{
    /*******************code*******************/
    int n = 15;
    int a1[15] = {1,
                  2, 3,
                  4, 5, NULL, NULL,
                  NULL, 6, 7, NULL, NULL, NULL, NULL, NULL};
    tree *root;
    CreatTree(root, a1, n, 0);
    fun_6_45(root, 4);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
